import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-04-16
 * Time: 19:49
 */

//二叉树的练习题
class BinaryTree {

    static class TreeNode{
        public char val;
        public TreeNode left;//存储左子树的引用
        public TreeNode right;//存储又子树的引用

        public TreeNode(char val){
            this.val = val;
        }
    }

    public TreeNode creakTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B = new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;

        return A;
    }
    //前序遍历
    public void preOrder(TreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.val + " ");
        preOrder(root.left);
        preOrder(root.right);
    }

    //相同的树
    public boolean isSameTree(TreeNode p, TreeNode q){
        //1.先判断结构是否一样
        if(p != null && q == null || p == null && q != null){
            return false;
        }
        //上述语句执行说明两个根节点同时为空或者同时不为空
        if(p == null && q == null){
            return true;
        }
        //判断值是否一样
        if(p.val != q.val){
            return false;
        }

        return isSameTree(p.left , q.left) && isSameTree(p.right, q.right);
    }

    //一个树是否是另一个树的子树
    public boolean isSubTree(TreeNode root , TreeNode subRoot){
        if(root == null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubTree(root.left, subRoot)){
            return true;
        }
        if(isSubTree(root.right, subRoot)){
            return true;
        }

        return false;
    }

    //判断是否是对称二叉树
    public boolean isSymmetric(TreeNode root){
        if(root == null){
            return true;
        }
        TreeNode leftTree = root.left;
        TreeNode rightTree = root.right;

        if(leftTree != null && rightTree == null ||  leftTree == null && rightTree != null){
            return false;
        }
        if(leftTree == null && rightTree == null){
            return true;
        }
        if(leftTree.val != rightTree.val){
            return false;
        }
        return isSubTree(leftTree.left , rightTree.right) &&
                isSubTree(leftTree.right , rightTree.left);
    }

    //判断是否为平衡二叉树
    /**什么是平衡二叉树?
     * 每一个节点的每一个左右子树的高度差<=1
     * //思路:
     * 遍历这颗树的每一个节点，求每一个节点的左树和右树的高度 发现高度大于2则直接返回false
     * && root的左树和右树是平衡的
     */
    //求树的高度(时间复杂度n^2)
    private int getHight(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHight = getHight(root.left);
        int rightHight = getHight(root.right);

        return Math.max(leftHight,rightHight) + 1;
    }

    public boolean isBlanced(TreeNode root){
        if(root == null){
            return true;
        }
        int leftHight = getHight(root.left);
        int rightHight = getHight(root.right);

        return Math.abs(leftHight - rightHight) < 2 &&
                isBlanced(root.left) && isBlanced(root.right);
    }

    //求树的高度(时间复杂度n)
    public boolean isBlanced2(TreeNode root){
        if(root == null){
            return true;
        }
        return getHeight2(root) >= 0;
    }

    private int getHeight2(TreeNode root){
        if(root == null){
            return 0;
        }
        int leftHeight = getHeight2(root.left);
        if(leftHeight < 0){
            return -1;
        }
        int rightHeight = getHeight2(root.right);
        if(rightHeight < 0){
            return -1;
        }
        if(Math.abs(leftHeight - rightHeight) <=1 ){
            return Math.max(leftHeight,rightHeight) + 1;
        }else {
            return -1;
        }
    }

    //构建二叉树，转化成链表结构
    public int i = 0;
    public TreeNode creatTree2(String str){
        TreeNode root = null;
        if(str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            i++;
            root.left = creatTree2(str);
            root.right = creatTree2(str);
        }else {
            i++;
        }
        return root;
    }

    public void inOrder(TreeNode root){
        if(root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //把二叉树转化成链表(中序遍历)
    TreeNode prve = null;
    public TreeNode covert(TreeNode root){
        if(root == null){
            return null;
        }
        converSon(root);

        TreeNode head = root;
        while(head.left != null){
            head = head.left;
        }

        return head;
    }

    public void converSon(TreeNode root){
        if(root == null){
            return;
        }
        converSon(root.left);
        root.left = prve;
        if(prve != null){
            prve.right = root;
        }
        prve = root;
        converSon(root.right);
    }

    //判断一颗树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null){
            return true;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;;
            }
        }

        while(!queue.isEmpty()){
            TreeNode peek = queue.peek();
            if(peek != null){
                return false;
            }
            queue.poll();
        }
        return true;
    }

    //寻找两个节点的最近的公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root , TreeNode p , TreeNode q){
        if(root == null){
            return null;
        }
        if(root == p || root == q){
            return root;
        }
        TreeNode leftTree = lowestCommonAncestor(root.left, p , q);
        TreeNode rightTree = lowestCommonAncestor(root.right, p , q);

        if(leftTree != null && rightTree != null){
            return root;
        }else if(leftTree != null){
            return leftTree;
        }else {
            return rightTree;
        }
    }

    //寻找两个节点的最近的公共祖先(栈的写法)
    public TreeNode lowestCommonAncestor2(TreeNode root , TreeNode p , TreeNode q){
        if(root == null){
            return null;
        }
        Stack<TreeNode> stackP = new Stack<>();
        Stack<TreeNode> stackQ = new Stack<>();

        getPath(root , p , stackP);
        getPath(root , q , stackQ);

        int sizeP = stackP.size();
        int sizeQ = stackQ.size();

        if(sizeP > sizeQ){
            int size = sizeP - sizeQ;
            while(size != 0){
                stackP.pop();
                size--;
            }
        }else {
            int size = sizeQ - sizeP;
            while(size != 0){
                stackQ.pop();
                size--;
            }
        }

        int size = sizeP;
        while(size != 0){
            if(stackP.peek() == stackQ.peek()){
                return stackP.peek();
            }
            stackP.pop();
            stackQ.pop();
        }
        return null;
    }

    private boolean getPath(TreeNode root , TreeNode node , Stack<TreeNode> stack) {
        if (root == null) {
            return false;
        }
        stack.push(root);
        if(root == node){
            return true;
        }
        boolean ret = getPath(root.left , node , stack);
        if(ret){
            return true;
        }
        ret = getPath(root.right , node , stack);
        if(ret){
            return true;
        }
        stack.pop();
        return false;
    }

    //根据前序遍历和中序遍历来构建二叉树
    public int preindex;
    public TreeNode buildTree(char[] perorder , char[] inorder){
        return buildTreeChild(perorder , inorder , 0 , inorder.length - 1);
    }

    private TreeNode buildTreeChild(char[] preorder , char[] inorder , int inbegin , int inend){
        if(inbegin > inend){
            return null;
        }
        TreeNode root = new TreeNode(preorder[preindex]);
        int rootIndex = findVal(inorder, inbegin , inend , preorder[preindex]);

        preindex++;

        root.left = buildTreeChild(preorder , inorder , inbegin , rootIndex - 1);
        root.right = buildTreeChild(preorder , inorder , rootIndex + 1 , inend);

        return root;
    }

    private int findVal(char[] inorder, int inbegin , int inend , int val){
        for(int i = inbegin ; i <= inend ; i++){
            if(inorder[i] == val){
                return i;
            }
        }
        return -1;
    }

    //将二叉树转化为字符串
    public void treeStrChild(TreeNode root){
        StringBuilder stringBuilder = new StringBuilder();
        if(root == null){
            return;
        }
        stringBuilder.append(root.val);

        if(root.left != null){
            stringBuilder.append("(");
            treeStrChild(root.left);
            stringBuilder.append(")");
        }else {
            if(root.right == null){
                return;
            }else {
                stringBuilder.append("()");
            }
        }

        if(root.right != null){
            stringBuilder.append("(");
            treeStrChild(root.right);
            stringBuilder.append(")");
        }else {
            return;
        }
    }
}
